package leetcode.editor.vscdev.hot100;

public class lc53 {
    
}
class Solution {
    public int maxSubArray(int[] nums) {
        return funcDP(nums);
    }
    private int funcGreedy(int[] nums){
        // 不断累加, 局部贪心.取最优值
        int res = Integer.MIN_VALUE;
        int temp = 0; 
        for (int i = 0; i < nums.length; i++){
            if (temp<=0){
                // 如果一部分的和已经小于等于0了,那么再累加它是没有意义的
                temp = nums[i];
            } else {
                temp += nums[i];
            }
            res = Math.max(res, temp);
        }
        return res;
    }
    private int funcDP(int[] nums){
        // dp[i] 定义为数组nums中以num[i]结尾的最大连续子串和
        // 即dp[i] = Math.max(dp[i-1]+nums[i], nums[i])
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int max = nums[0];
        for (int i = 1; i<nums.length; i++){
            dp[i] = Math.max(dp[i-1]+nums[i], nums[i]);
            if (dp[i]>max){
                max = dp[i];
            }
        }
        return max;
    }
}